package pri.zxx.learndemo.javabase.tree;

import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.LinkedList;

@Slf4j
public class TreeList {

	private TreeNode root;

	static class TreeNode {
		private int key;
		private String value;
		private TreeNode left;
		private TreeNode right;

		public TreeNode(int key, TreeNode left, TreeNode right) {
			this.key = key;
			this.left = left;
			this.right = right;
		}

		public TreeNode(int key, String value, TreeNode left, TreeNode right) {
			this.key = key;
			this.value = value;
			this.left = left;
			this.right = right;
		}
	}

	public void add(int v) {


		TreeNode now = new TreeNode(v, new TreeNode(2, null, null), new TreeNode(3, null, null));
		if (root == null) {
			root = now;
		} else {
			//ToDo find position

		}
	}

	public void printPre() {
		LinkedList<TreeNode> stack = new LinkedList<>();
		TreeNode now = root;
		TreeNode last = null;
		while (now != null || stack.size() > 0) {
			if (now != null) {
				stack.addFirst(now);
				log.info("先中：{}", now.value);
				now = now.left;
			} else {
				TreeNode parent = stack.getFirst();
				if (parent.right == null) {
					last = stack.removeFirst();
					log.error("后：{}", parent.value);
				} else if (parent.right == last) {
					last = stack.removeFirst();
					log.error("后：{}", parent.value);
				} else {
					log.warn("中：{}", parent.value);
					now = parent.right;
				}
			}
		}

	}

	public void printPre(TreeNode treeNode) {
		if (treeNode != null) {
			System.out.print(treeNode.value + "\n");
			printPre(treeNode.left);
			printPre(treeNode.right);
		}
	}

	public void printMiddle(TreeNode treeNode) {
		if (treeNode != null) {
			printMiddle(treeNode.left);
			System.out.print(treeNode.value + "\n");
			printMiddle(treeNode.right);
		}
	}

	public void printPost(TreeNode treeNode) {
		if (treeNode != null) {
			printPost(treeNode.left);
			printPost(treeNode.right);
			System.out.print(treeNode.value + "\n");
		}
	}

	public static void main(String[] args) {
		TreeList t = new TreeList();

		t.add(1);
		t.printPre();

	}

	@Test
	public void test() {

		int[] preOrder = {1, 2, 4, 3, 6, 7};
		int[] inOrder = {4, 2, 1, 6, 3, 7};
		TreeNode treeNode = buildTree(preOrder, inOrder);
		printPre(treeNode);
	}

	public TreeNode buildTree(int[] preOrder, int[] inOrder) {
		if (preOrder.length == 0 || inOrder.length == 0) {
			return null;
		}
		int rootV = preOrder[0];
		TreeNode root = new TreeNode(rootV, null, null);
		for (int i = 0; i < inOrder.length; i++) {
			if (inOrder[i] == rootV) {
				int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
				int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);
				int[] preLeft = Arrays.copyOfRange(preOrder, 1, i + 1);
				int[] preRight = Arrays.copyOfRange(preOrder, i + 1, inOrder.length);
				root.left = buildTree(preLeft, inLeft);
				root.right = buildTree(preRight, inRight);
				break;
			}
		}
		return root;
	}
}
